#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef _Bool Map;
typedef struct LIST List;
typedef struct STACK Stack;
typedef int ElementType;
typedef struct QUEUE Queue;
struct LIST{
	int elm;
	List *next;
	List *tail;
};

struct STACK{
	ElementType elm;
	Stack* next;	
};

struct QUEUE{
	ElementType elm;
	Queue* next;
	Queue* tail;
};

List *ListInit(void);
_Bool ListEmpty(List*);
void Add(List*,int);
void printList(List*);
//int  Get(List*,int);
Stack* StackInit(void);
_Bool StackEmpty(Stack*);
void Push(Stack*,ElementType);
ElementType Pop(Stack*);
Queue *QueueInit(void);
_Bool QueueEmpty(Queue*);
void EnQueue(Queue*,ElementType);
ElementType DeQueue(Queue*);
List *DFS(int n,Map(*)[n],int*,int,int);
//List *DFS(Map **map,int* visited,int n,int mark,int index){
List *BFS(int n,Map(*)[n],int*,int,int);
int NextUnVisited(int n,Map (*map)[n],int *visited,int mark,int index);


int main(void){
	int n,m;
	scanf("%d %d",&n,&m);
	Map map[n][n];
	int visited[n];
	for(int i=0;i<n;i++){
		visited[i]=0;
		for(int j=0;j<n;j++)
			map[i][j]=false;
	}
	int i1,i2;
	for(int i=0;i<m;i++){
		scanf("%d %d",&i1,&i2);
		map[i1][i2]=map[i2][i1]=true;
	}
	int mark=0;
	for(int i=0;i<n;i++){
		if( visited[i] == 0 ){
			List *l=DFS(n,map,visited,++mark,i);
			printList(l);
		}
	}
	mark=0;
	for(int i=0;i<n;i++)
		visited[i]=0;
	for(int i=0;i<n;i++){
		if( visited[i] == 0 ){
			List *l=BFS(n,map,visited,++mark,i);
			printList(l);
		}
	}
	return 0;
}
Stack* StackInit(void){
	Stack *ret=malloc(sizeof(Stack));
	ret->next=NULL;
	return ret;
}
_Bool StackEmpty(Stack *s){
	if( s->next )
		return false;
	return true;
}
void Push(Stack *s,ElementType elm){
	Stack *new=malloc(sizeof(Stack));
	new->elm=elm;
	new->next=s->next;
	s->next=new;
	return;
}
ElementType Pop(Stack *s){
	ElementType e=s->next->elm;
	Stack *t=s->next;
	s->next=s->next->next;
	free(t);
	return e;
}
List *ListInit(void){
	List *l=malloc(sizeof(List));
	l->next=NULL;
	l->tail=l;
	return l;
}
_Bool ListEmpty(List* l){
	if( l->next )
		return false;
	return true;
}
void Add(List* l,int e){
	List *new=malloc(sizeof(List));
	new->elm=e;
	new->next=NULL;
	l->tail->next=new;
	l->tail=new;
	return;
}

void printList(List *l){
	printf("{ ");
	while(l->next){
		printf("%d ",l->next->elm);
		l=l->next;
	}
	printf("}\n");
}
Queue *QueueInit(void){
	Queue *q=malloc(sizeof(Queue));
	q->next=NULL;
	q->tail=q;
	return q;
}
_Bool QueueEmpty(Queue* q){
	if( q->next )
		return false;
	return true;
}
void EnQueue(Queue* q,ElementType elm){
	Queue *new=malloc(sizeof(Queue));
	new->elm=elm;
	new->next=NULL;
	q->tail->next=new;
	q->tail=new;
	return;
}
ElementType DeQueue(Queue *q){
	ElementType e=q->next->elm;
	Queue *t=q->next;
	q->next=q->next->next;
	free(t);
	if( !(q->next) )
		q->tail=q;
	return e;
}

int NextUnVisited(int n,Map (*map)[n],int *visited,int mark,int index){
	for(int i=0;i<n;i++){
		if(map[index][i] && visited[i]!= mark)
			return i;
	}
	return -1;
}
List *DFS(int n,Map (*map)[n],int* visited,int mark,int index){
	List *l=ListInit();
	Stack *s=StackInit();
	Push(s,index);
	while( !StackEmpty(s) || -1!=NextUnVisited(n,map,visited,mark,index) ){
		if( visited[index] != mark ){
			visited[index]=mark;
			Add(l,index);
			//Push(s,index);
		}
		int i=NextUnVisited(n,map,visited,mark,index);
		if( -1==i ){
			index=Pop(s);
		}else{
			index=i;
			Push(s,index);
		}
	}
	return l;
}
//List *BFS(Map,int*,int);
List *BFS(int n,Map(*map)[n],int* visited,int mark,int index){
	List *l=ListInit();
	Queue *q=QueueInit();
	EnQueue(q,index);
	visited[index]=mark;
	ElementType e,t;
	while( !QueueEmpty(q) ){
		e=DeQueue(q);
		Add(l,e);
		t=NextUnVisited(n,map,visited,mark,e);
		while( t!=-1 ){
			visited[t]=mark;
			EnQueue(q,t);	
			t=NextUnVisited(n,map,visited,mark,e);
		}
	}
	return l;
}
